package edu.gatech.cc.hwa.server.math;

import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.MathContext;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Polynomial {

	private final static MathContext MATH_CONTEXT = new MathContext(512);
	
	public static Polynomial generatePolynomialOfDegreeNForHpwd(int n, BigInteger hpwd) {
		List<BigInteger> list = new ArrayList<BigInteger>(n+1);
		list.add(hpwd);
		for(int i=1;i<=n;i++) {
			list.add(randomPositive128BitInteger());
		}
		return new Polynomial(list);
	}

	public static BigInteger interpolate(Map<Integer, BigInteger> xyPairs) {
		BigDecimal sum = BigDecimal.ZERO;
		for(Integer i : xyPairs.keySet()) {
			BigDecimal y = new BigDecimal(xyPairs.get(i), MATH_CONTEXT);
			sum = sum.add(y.multiply(lagrange(i, xyPairs.keySet()), MATH_CONTEXT));
		}
		BigInteger sumInt = getBigIntFromBigDec(sum);
		return sumInt.mod(UsefulNumbers.Q);
	}
	
	private static BigInteger getBigIntFromBigDec(BigDecimal bd) {
		String bdString = bd.toPlainString();
		int decPoint = bdString.indexOf('.');
		return (decPoint == -1) ? (new BigInteger(bdString)) : (new BigInteger(bdString.substring(0, decPoint)));
	}
	
	private static BigDecimal lagrange(Integer i, Set<Integer> xSet) {
		BigDecimal product = BigDecimal.ONE;
		for(Integer j : xSet) {
			if (j.compareTo(i) != 0) {
				BigDecimal bdJ = new BigDecimal(j, MATH_CONTEXT);
				BigDecimal bigDenom = new BigDecimal((double)(j-i), MATH_CONTEXT);
				BigDecimal l = bdJ.divide(bigDenom, MATH_CONTEXT);
				product = product.multiply(new BigDecimal(l.toString(), MATH_CONTEXT));
			}
		}
		return product;
	}
	
	private static BigInteger randomPositive128BitInteger() {
		BigInteger two = new BigInteger("2");
		BigInteger val = new BigInteger("2");
		int bits = 128;
		val = val.pow(bits-1);
		for (int i=1;i<(bits-1);i++) {
			if (Math.random() <.5) {
				val = val.add(two.pow(i));
			}
		}
		return val;
	}
	
	private final List<BigInteger> coefficientValues;
	
	/**
	 * Coefficient values should be ordered in lowest to highest exponent.
	 * [c1x^0, c2x^1, ... cnx^n]
	 * @param coefficientValues
	 */
	public Polynomial(BigInteger[] coefficientValues) {
		this(Arrays.asList(coefficientValues));
	}
	
	/**
	 * Coefficient values should be ordered in lowest to highest exponent.
	 * [c1x^0, c2x^1, ... cnx^n]
	 * @param coefficientValues
	 */
	public Polynomial(List<BigInteger> coefficientValues) {
		this.coefficientValues = new ArrayList<BigInteger>(coefficientValues);
	}
	
	public BigInteger evaluateAtX(Integer x, BigInteger mod) {
		BigInteger sum = BigInteger.ZERO;
		Integer i = 0;
		BigInteger bigIntX = new BigInteger(x.toString());
		for (BigInteger c : coefficientValues) {
			sum = bigIntX.pow(i++).multiply(c).add(sum);
		}
		return sum;
	}
}
